//
// Created by Incredible on 17/3/21.
//

#ifndef UNIONFIND2_UNIONFIND6_H
#define UNIONFIND2_UNIONFIND6_H

/**
 * 采用路径压缩，提高find效率
 * 实现方法 2：利用递归将每个节点的父亲更新为根节点，树高度为2
 */

#include <cassert>

namespace UF6 {


    using namespace std;

    class UnionFind {

    //private:
    public:
        int *parent; //节点的父节点，向上搜索根节点，当parent[i] == i 时 ，该节点为根节点
        int *rank; //rank[i]标识根节点为i的树的高度
        int count; //数组大小

    public:

        //初始化并查集
        UnionFind(int count) {
            this->count = count;
            parent = new int[count];
            rank = new int[count];

            //将每个节点的根设置为自己，标识其没有根节点，自己就是根
            for (int i = 0; i < count; ++i) {
                parent[i] = i;
                rank[i] = 1;    // 1. 1为初始该节点的层数为1
                // 2. 作用：用该数组保存该根节点为i的树的高度，在进行合并的时候，将树高度rank[i]小的根节点的父节点更新为rank[i]多的节点
            }
        }

        //析构函数(对所有new 开辟的空间进行释放)
        ~UnionFind() {
            delete[] parent;
            delete[] rank;
        }

        //查找x的根节点
        int find(int x) {
            //断言 x 是否越界
            assert(x >= 0 && x < count);


            //TODO 路径压缩
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
                rank[x] = 2;
            }
            rank[parent[x]] = 1;
            return parent[x];

//      int px = parent[x]; //px 为x的父节点
//        while (px != x) {        //如果x的父节点不是根节点，继续向上寻找,
//
//            //压缩：将父节点不为根节点的节点向上提升，减少树的高度，并维护rank数组
//            parent[x] = parent[px];
//
//            //维护rank[x]
//            rank[x] -= 1;
//
//            x = parent[x];
//            px = parent[x];
//        }
//        return x;
        }

        //判断两个节点是否有关联
        bool isConnection(int x, int y) {
            return find(x) == find(y);
        }

        //联合x,y
        void unionElements(int x, int y) {

            //找出需要联合的两个节点的根节点
            int xRoot = find(x);
            int yRoot = find(y);

            //x , y 就是联合的
            if (xRoot == yRoot) {
                return;
            }

            //优化点：
            //将rank[xRoot]与rank[yRoot]中较小的一方的根节点进行更新，减少树的高度，提高搜索效率
            if (rank[xRoot] < rank[yRoot]) {

                //将x的根更新为y的根节点
                parent[xRoot] = yRoot;
            } else if (rank[xRoot] > rank[yRoot]) {

                //将y的根更新为y的根节点
                parent[yRoot] = xRoot;
            } else {  //rank[xRoot] == rank[yRoot]
                //将x的根更新为y的根节点
                parent[xRoot] = yRoot;

                //维护rank数组，层数+1
                rank[yRoot] += 1;
            }
        }

    };

}

#endif //UNIONFIND2_UNIONFIND6_H
